Part I Multivariate normal distribution

Let \(\boldsymbol{x} = (x_1, \dots, x_n), n = 100\) be multivariate normal distributed with \(E(x_i) = 0, Var(x_i) = 1\), and \(Corr(x_i, x_j) = e^{-0.1|i - j|}\)

  1. Compute and image the covariance matrix \(\boldsymbol{\Sigma}\) of \(\boldsymbol{x}\)

  2. Find the lower Cholesky factor \(\boldsymbol{L}\), such that \(\boldsymbol{L}\boldsymbol{L}^T = \boldsymbol{\Sigma}\), of this covariance matrix, and image.

  3. Sample \(\boldsymbol{x} = \boldsymbol{Lz}\), where \(\boldsymbol{z}\) is a length n random vector of independent standard normal variables. Plot the sample.

  4. Find the precision matrix \(\boldsymbol{Q}\) of the covariance matrix, and compute the lower Cholesky factor \(\boldsymbol{L}_Q\), such that \(\boldsymbol{L}_Q\boldsymbol{L}_Q^T = \boldsymbol{Q}\), of this matrix. Image these matrices and compare them to the images obtained in a) and b)

  5. Sample \(\boldsymbol{x}\) by solving \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\), where \(\boldsymbol{z}\) is a length n random vector of independen standard normal variables. Plot the sample.

  6. Permute the ordering of variables in \(\boldsymbol{x}\), and redo the exercises.


Solution to Part I

a)

Given that \(\boldsymbol{\Sigma} = e^{-0.1|i - j|}\). The covariance matrix can be expressed as follows: \[\begin{equation*} \Sigma = \begin{pmatrix} 1 & e^{- 0.1 h_{12}} &\dots & e^{- 0.1 h_{1n}} \\ e^{- 0.1 h_{21}} & 1 & \dots & e^{- 0.1 h_{2n}} \\ \vdots & \vdots & \ddots & \vdots \\ e^{- 0.1 h_{n1}} & e^{- 0.1 h_{n2}} & \dots & 1 \end{pmatrix} \end{equation*}\]

### b) According to the cholesky decomposition rule, \(\boldsymbol{L}\) is the lower triangular matrix for \(\boldsymbol{\Sigma}\), it can be easily computed from R using L = chol(Sigma). It is then plotted as below.

c)

Sample using \(\boldsymbol{x} = \boldsymbol{L}\boldsymbol{z}\) transforms the zero-mean, standard normal random variales to the random variables with the desired covariance matrix.

d)

The precision matrix \(\boldsymbol{Q}\) is the inverse of the covariance matrix \(\boldsymbol{\Sigma}\), it is computed using Q = solve(Sigma) in R. The three matrices are thereby depicted as follows. Since the covariance matrix is not singular, given that the it belongs to the Matern family, thus it is analytically guaranteed to have positive definite property. Therefore, both precision matrix and the lower triangular precision matrix exist.

e)

Similarly, the expected random samples can be generated using the inversion of the above formula, thus \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\)

f)

Permute \(\boldsymbol{x}\) to make randomise the ordering of the grid, the asscociated covariance matrix can be thereby modified in a sparse way.

Part II Gaussian random fields and Kriging

The purpose of this computer exercise is to give an introduction to parameter estima- tion and kriging for Gaussian random field models for spatial data.

We assume the following observation model on the unit square:

\[\begin{equation*} y(\boldsymbol{s}_j) = x(\boldsymbol{s}_j) + \epsilon_j, \ \ \ j = 1, \dots, N, \end{equation*}\]

where \(\epsilon_j ~ \mathop{N}(0, \tau^2)\) are independent measurement noise terms. Further, consider a Matérn covariance function for the Gaussian random field \(\boldsymbol{x(s)}\):

\[\begin{equation*} Cov(x(\boldsymbol{s}_i), x(\boldsymbol{s}_j)) = \Sigma_{i, j} = \sigma^2(1 + \phi h)\exp(-\phi h), \end{equation*}\]

where \(h\) denotes the Euclidean distance between the two sites \(\boldsymbol{s}_i\) and \(\boldsymbol{s}_j\).

We assume the mean increases with east and north coordinates as follows: \(\mu_j = \alpha((s_{j1} - 0.5) + (s_{j2} - 0.5))\), for site \(\boldsymbol{s}_j = (s_{j1}, s_{j2})\) on the unit square.


2.1 Simulation

Simulate \(N = 200\) random sites in the unit square and plot them. Form the covariance matrix using \(\sigma = 1, \phi = 10, \tau = 0.05\). Take its Cholesky decomposition and simulate dependent zero-mean Gaussian data variables, then add the mean using \(\alpha = 1\). Plot your observations.

The true mean of the field is expressed as \[\begin{equation*} \mu_i = \alpha((s_{i1} - 0.5) + (s_{i2} - 0.5)) = -\alpha + \alpha s_{i1} + \alpha s_{i2} = \underbrace{ \begin{bmatrix} 1 & s_{i1} & s_{i2} \\ \end{bmatrix}}_{\boldsymbol{h}^T(\boldsymbol{s}_i)} \underbrace{ \begin{bmatrix} -\alpha \\ \alpha \\ \alpha \end{bmatrix}}_{\boldsymbol{\beta}} \end{equation*}\] where \(s_{i1}, s_{i2}\) are the location from east and north direction in the grid.


2.2 Paramter estimation

We will now use the simulated data to estimate the model parameters \(\alpha, \sigma^2, \tau^2, \phi\) using maximum likelihood estimation. Iterate between the update for the mean parameter, and updating the covariance parameters. Monitor the likelihood function at each step of the algorithm to check convergence.

The mean of the field is modelled by \(p(\boldsymbol{x})\) and the imperfect information \(\boldsymbol{y} = (y_1, \dots, y_m)\) conditional on \(\boldsymbol{x}\) can be modelled by \(p(\boldsymbol{y}|\boldsymbol{x})\), which can be expressed as follows: \[\begin{equation*} p(\boldsymbol{x}) = \mathop{N}(\boldsymbol{H}\beta, \boldsymbol{\Sigma}), \quad p(\boldsymbol{y}|\boldsymbol{x}) = \mathop{N}(\boldsymbol{Fx}, \boldsymbol{T}) \end{equation*}\] Therefore, the marginal likelihood of the data is \[\begin{equation*} p(\boldsymbol{y}) = \mathop{N}(\boldsymbol{G\beta}, \boldsymbol{C}), \quad \boldsymbol{G} = \boldsymbol{FH}, \quad \boldsymbol{C} = \boldsymbol{F\Sigma F^T} + \boldsymbol{T} \end{equation*}\] The log-likelihood as a function of \(\beta\) and unknown fixed nuisance parameters \(\boldsymbol{\theta}\) in the prior covariance matrix \(\boldsymbol{\Sigma} = \boldsymbol{\Sigma(\boldsymbol{\theta})}\), and/or the likelihood noise matrix \(\boldsymbol{T} = \boldsymbol{T}(\boldsymbol{\theta})\) becomes \[\begin{equation*} l(\boldsymbol{\theta}, \boldsymbol{\beta}) = -\frac{m}{2} \log(2\pi) - \frac{1}{2}\log|\boldsymbol{C}| - \frac{1}{2}(\boldsymbol{y} - \boldsymbol{G}\boldsymbol{\beta})^T\boldsymbol{C}^{-1}(\boldsymbol{y} - \boldsymbol{G\beta}) \end{equation*}\]

The MLEs of \(\boldsymbol{\beta}\) and \(\boldsymbol{\theta}\) are obtained by \[\begin{equation*} (\hat{\boldsymbol{\beta}}, \hat{\boldsymbol{\theta}}) = \underset{\boldsymbol{\beta}, \boldsymbol{\theta}}{\arg\max}\{l(\boldsymbol{\beta, \theta})\} \end{equation*}\] For fixed \(\boldsymbol{\theta}\), the MLEs of \(\boldsymbol{\beta}\) can be determined analytically. \[\begin{equation*} \frac{dl}{d\boldsymbol{\beta}} = \boldsymbol{G}^T\boldsymbol{C}^{-1}\boldsymbol{y} - \boldsymbol{G}^T\boldsymbol{C}^{-1}\boldsymbol{G}\boldsymbol{\beta} = \boldsymbol{0}, \quad \hat{\boldsymbol{\beta}} = (\boldsymbol{G}^T\boldsymbol{C}^{-1}\boldsymbol{G})^{-1}\boldsymbol{G}^T\boldsymbol{C}^{-1}\boldsymbol{y} \end{equation*}\] Whereas for fixed \(\boldsymbol{\beta}\), the MLE of nuisance parameters \(\boldsymbol{\theta}\) can be obtained by numerical maximization. Let \(\boldsymbol{z} = \boldsymbol{y} - \boldsymbol{G\beta}\), and \(\boldsymbol{Q} = \boldsymbol{C}^{-1}\). For each component of \(\boldsymbol{\theta}_r\), \(r = 1, \dots, d\), in this case, \(\theta\) has 3 components (\(\sigma^2, \eta, \tau^2\)). The score of the log-likelihood becomes \[\begin{equation*} \frac{dl}{d\theta_r} = -\frac{1}{2}\text{trace}(\boldsymbol{Q}\frac{d\boldsymbol{C}}{d\theta_r}) + \frac{1}{2}\boldsymbol{z}^T\boldsymbol{Q}\frac{d\boldsymbol{C}}{d\theta_r}\boldsymbol{Qz} \end{equation*}\]

The above mentioned score can be solved iteratively using Fisher scoring algorithm. To achieve the numerical stability, the expected Hessian is applied, which is \[\begin{equation*} \mathop{E}(\frac{d^2l}{d\theta_rd\theta_{\bar{r}}}) = -\frac{1}{2}\text{trace}(\boldsymbol{Q}\frac{d\boldsymbol{C}}{d\theta_{\bar{r}}}\boldsymbol{Q}\frac{d\boldsymbol{C}}{d\theta_r}) \end{equation*}\]

## [1] "1.16100274094671  , iter no is  0"
## [1] "0.0983478023616246  , iter no is  1"
## [1] "0.0637476756371519  , iter no is  2"
## [1] "0.0330323876752982  , iter no is  3"
## [1] "0.0216765191888463  , iter no is  4"

## 
## Estimated sigma is  0.785 ; True sigma is  1 
## Estimated phi is  12.72 ; True phi is  10 
## Estimated tau is  -0.06224 ; True tau is  0.05 
## Estimated beta1 is  -1.47 ; True beta1 is  -1 
## Estimated beta2 is  1.63 ; True beta2 is  1 
## Estimated beta3 is  1.88 ; True beta3 is  1NULL

2.3 Kriging

We will now use the estimated model parameters to perform kriging prediction. Predict variables \(x(s)\), where predictions sites lie on a regular grid of size 25x25 for the unit square. Visualize the Kriging surface and the prediction standard error. Compare with the true field.

## [1] "The prediction error is  0.303326130373502"

Part III Integrated nested Laplace Approximations (INLA)

3.1 Simple Linear Regression

In the last part of this exercise we explore the R-INLA package.

The ski jumping data set contains 26 observations of measured lengths in ski jumping competitions (in meters) between 1961 and 2011.

\label{fig:skiData}Visualisation of the ski jumping data set

Visualisation of the ski jumping data set

In Figure we observe a clear (almost linear) trend in the measured jumping lengths to increase with the years.

Therefore, we use linear approach for the statistical modelling of this data, where the years \(x_i\) are the covariates and the lengths \(y_i\) are the responses for \(i=1,\dots,26\): \[\begin{equation*} \mathbb{E}[y_i] = \mu + \beta x_i,\quad \mathbb{Var}[y_i]=\tau^{-1}. \end{equation*}\]

This can be posed as a latent Gaussian model suited for the INLA framework.

  1. The response depends on the linear predictors \(\eta\) as \(y|x,\theta = \Pi \pi(y_i|\eta_i,\tau)\) where \(\pi(y_i|\eta_i,\tau)\sim\mathcal{N}(\eta_i,\tau^{-2})\)
  2. The parameter of the linear predictor \(eta_i=\mu+x_i\beta\) are independent Gaussian with some variance and mean zero.
  3. The hyperparameter \(\tau\) is only one-dimensional.
## 
## Call:
##    "inla(formula = Length ~ Year, data = skiData)" 
## Time used:
##     Pre = 4.73, Running = 0.494, Post = 0.259, Total = 5.48 
## Fixed effects:
##                  mean      sd 0.025quant  0.5quant 0.975quant      mode kld
## (Intercept) -4029.646 106.615  -4240.649 -4029.650  -3818.934 -4029.646   0
## Year            2.126   0.054      2.019     2.126      2.232     2.126   0
## 
## Model hyperparameters:
##                                          mean   sd 0.025quant 0.5quant
## Precision for the Gaussian observations 0.072 0.02      0.038     0.07
##                                         0.975quant  mode
## Precision for the Gaussian observations      0.116 0.066
## 
## Expected number of effective parameters(stdev): 2.00(0.00)
## Number of equivalent replicates : 13.00 
## 
## Marginal log-Likelihood:  -89.58
\label{fig:INLA}Posterior marginals for selected effects

Posterior marginals for selected effects

## Mean            3.83993 
## Stdev           0.552976 
## Quantile  0.025 2.93482 
## Quantile  0.25  3.44617 
## Quantile  0.5   3.77761 
## Quantile  0.75  4.16357 
## Quantile  0.975 5.09958

FB: What does all this mean?…..

3.2 GLMM with random effects

Last, we use INLA to analyse the “Seeds” data set.

## 
## Call:
##    c("inla(formula = formula, family = \"binomial\", data = data, Ntrials 
##    = n, ", " control.predictor = list(compute = TRUE), control.family = 
##    list(link = \"logit\"))" ) 
## Time used:
##     Pre = 5.06, Running = 0.456, Post = 0.251, Total = 5.77 
## Fixed effects:
##               mean    sd 0.025quant 0.5quant 0.975quant   mode kld
## (Intercept) -0.429 0.115     -0.656   -0.429     -0.204 -0.428   0
## x1          -0.272 0.156     -0.580   -0.272      0.033 -0.271   0
## x2           1.066 0.146      0.782    1.066      1.353  1.065   0
## 
## Random effects:
##   Name     Model
##     plate IID model
## 
## Model hyperparameters:
##                         mean       sd 0.025quant 0.5quant 0.975quant mode
## Precision for plate 18930.69 20071.40      30.63 12701.76   73765.97 7.83
## 
## Expected number of effective parameters(stdev): 3.25(1.16)
## Number of equivalent replicates : 6.46 
## 
## Marginal log-Likelihood:  -73.75 
## Posterior marginals for the linear predictor and
##  the fitted values are computed

LS0tCnRpdGxlOiAiUHJvamVjdDIiCnN1YnRpdGxlOiAiR2F1c3NpYW4gcmFuZG9tIGZpZWxkIHdpdGggYXBwbGljYXRpb24gb2YgSU5MQSIKYXV0aG9yOiAkXG92ZXJzZXR7XG1hdGhybXt5YW9saW4uZ2VAbnRudS5ub319ezEwMDI2fSQgXGFuZAogICAgICAgICRcb3ZlcnNldHtcbWF0aHJte2Zsb3JpYW4uYmVpc2VyQG50bnUubm99fXsxMDAyNn0kCm91dHB1dDoKICAjIHBkZl9kb2N1bWVudDoKICAjICAgdG9jOiB0cnVlCiAgIyAgIHRvY19kZXB0aDogMwogICMgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogeWVzCiAgICBjb2RlX2Rvd25sb2FkOiB5ZXMKICAgIHRvY19kZXB0aDogMwogIGlvc2xpZGVzX3ByZXNlbnRhdGlvbjogZGVmYXVsdAogIGJlYW1lcl9wcmVzZW50YXRpb246CiAgICBzbGlkZV9sZXZlbDogMQogICAga2VlcF90ZXg6IHllcwogIHBkZl9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgICB0b2NfZGVwdGg6IDIKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1UUlVFLGVjaG89RkFMU0V9CnN1cHByZXNzUGFja2FnZVN0YXJ0dXBNZXNzYWdlcyhsaWJyYXJ5KGtuaXRyKSkKa25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBGQUxTRSwgbWVzc2FnZT1GQUxTRSx3YXJuaW5nID0gRkFMU0UsIGVycm9yID0gRkFMU0UpCmBgYAoKYGBge3IgbG9hZCBsaWJyYXJpZXMsIGVjaG8gPSBGfQpsaWJyYXJ5KGxhdHRpY2UpCmxpYnJhcnkodmlyaWRpc0xpdGUpCmNvdWwgPC0gdmlyaWRpcygxMDApCmBgYAoKIyBQYXJ0IEkgTXVsdGl2YXJpYXRlIG5vcm1hbCBkaXN0cmlidXRpb24KTGV0ICRcYm9sZHN5bWJvbHt4fSA9ICh4XzEsIFxkb3RzLCB4X24pLCBuID0gMTAwJCBiZSBtdWx0aXZhcmlhdGUgbm9ybWFsIGRpc3RyaWJ1dGVkIHdpdGggJEUoeF9pKSA9IDAsIFZhcih4X2kpID0gMSQsIGFuZCAkQ29ycih4X2ksIHhfaikgPSBlXnstMC4xfGkgLSBqfH0kCgphKSBDb21wdXRlIGFuZCBpbWFnZSB0aGUgY292YXJpYW5jZSBtYXRyaXggJFxib2xkc3ltYm9se1xTaWdtYX0kIG9mICRcYm9sZHN5bWJvbHt4fSQKCmIpIEZpbmQgdGhlIGxvd2VyIENob2xlc2t5IGZhY3RvciAkXGJvbGRzeW1ib2x7TH0kLCBzdWNoIHRoYXQgJFxib2xkc3ltYm9se0x9XGJvbGRzeW1ib2x7TH1eVCA9IFxib2xkc3ltYm9se1xTaWdtYX0kLCBvZiB0aGlzIGNvdmFyaWFuY2UgbWF0cml4LCBhbmQgaW1hZ2UuCgpjKSBTYW1wbGUgJFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7THp9JCwgd2hlcmUgJFxib2xkc3ltYm9se3p9JCBpcyBhIGxlbmd0aCBuIHJhbmRvbSB2ZWN0b3Igb2YgaW5kZXBlbmRlbnQgc3RhbmRhcmQgbm9ybWFsIHZhcmlhYmxlcy4gUGxvdCB0aGUgc2FtcGxlLgoKZCkgRmluZCB0aGUgcHJlY2lzaW9uIG1hdHJpeCAkXGJvbGRzeW1ib2x7UX0kIG9mIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCwgYW5kIGNvbXB1dGUgdGhlIGxvd2VyIENob2xlc2t5IGZhY3RvciAkXGJvbGRzeW1ib2x7TH1fUSQsIHN1Y2ggdGhhdCAkXGJvbGRzeW1ib2x7TH1fUVxib2xkc3ltYm9se0x9X1FeVCA9IFxib2xkc3ltYm9se1F9JCwgb2YgdGhpcyBtYXRyaXguIEltYWdlIHRoZXNlIG1hdHJpY2VzIGFuZCBjb21wYXJlIHRoZW0gdG8gdGhlIGltYWdlcyBvYnRhaW5lZCBpbiBhKSBhbmQgYikKCmUpIFNhbXBsZSAkXGJvbGRzeW1ib2x7eH0kIGJ5IHNvbHZpbmcgJFxib2xkc3ltYm9se0x9X1FeVFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7en0kLCB3aGVyZSAkXGJvbGRzeW1ib2x7en0kIGlzIGEgbGVuZ3RoIG4gcmFuZG9tIHZlY3RvciBvZiBpbmRlcGVuZGVuIHN0YW5kYXJkIG5vcm1hbCB2YXJpYWJsZXMuIFBsb3QgdGhlIHNhbXBsZS4KCmYpIFBlcm11dGUgdGhlIG9yZGVyaW5nIG9mIHZhcmlhYmxlcyBpbiAkXGJvbGRzeW1ib2x7eH0kLCBhbmQgcmVkbyB0aGUgZXhlcmNpc2VzLiAKCgoqKioKCiMjIFNvbHV0aW9uIHRvIFBhcnQgSQoKIyMjIGEpIApHaXZlbiB0aGF0ICRcYm9sZHN5bWJvbHtcU2lnbWF9ID0gZV57LTAuMXxpIC0ganx9JC4gVGhlIGNvdmFyaWFuY2UgbWF0cml4IGNhbiBiZSBleHByZXNzZWQgYXMgZm9sbG93czoKXGJlZ2lue2VxdWF0aW9uKn0KICAgIFxTaWdtYSA9IFxiZWdpbntwbWF0cml4fSAKICAgIDEgJiAgZV57LSAwLjEgaF97MTJ9fSAmXGRvdHMgJiBlXnstIDAuMSBoX3sxbn19IFxcCiAgICBlXnstIDAuMSBoX3syMX19ICYgMSAmIFxkb3RzICYgZV57LSAwLjEgaF97Mm59fSBcXAogICAgXHZkb3RzICYgXHZkb3RzICYgXGRkb3RzICYgXHZkb3RzIFxcCiAgICBlXnstIDAuMSBoX3tuMX19ICYgZV57LSAwLjEgaF97bjJ9fSAmIFxkb3RzICYgMQogICAgXGVuZHtwbWF0cml4fQpcZW5ke2VxdWF0aW9uKn0KCmBgYHtyIGNvdmFyaWFuY2UgbWF0cml4LCBlY2hvID0gRiwgZmlnLmFsaWduPSdjZW50ZXInfQojIHNpemVzCm4gPC0gMTAwCgojIGRlZmluZSByZWd1bGFyIGdyaWQgb2YgbG9jYXRpb25zCnNpdGVzMXYgPC0gYXJyYXkoKDE6biksYyhuLDEpKQoKIyBQcmlvciBtZWFuCm0gPC0gMAojIGNvbXB1dGUgRWFzdCBhbmQgTm9ydGggZGlzdGFuY2VzIG9uIGdyaWQKd3cgPC0gYXJyYXkoMSxjKG4sMSkpCgojIGRldGVybWluZSB0aGUgZGlzdGFuY2UgbWF0cml4CkggPC0gYWJzKHNpdGVzMXYlKiV0KHd3KS13dyAlKiUgdChzaXRlczF2KSkKCiMgRXhwb25lbnRpYWwgY292YXJpYW5jZSBtb2RlbApTaWdtYSA8LSBleHAoLTAuMSpIKQoKIyBQbG90IHRoZSBjb3ZhcmlhbmNlIG1hdHJpeApsZXZlbHBsb3QodChTaWdtYSksIAogICAgICAgICAgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkNvdmFyaWFuY2UgbWF0cml4IiwKICAgICAgICAgIHlsaW09YygxMDAsMSkpCmBgYAojIyMgYikgCkFjY29yZGluZyB0byB0aGUgY2hvbGVza3kgZGVjb21wb3NpdGlvbiBydWxlLCAkXGJvbGRzeW1ib2x7TH0kIGlzIHRoZSBsb3dlciB0cmlhbmd1bGFyIG1hdHJpeCBmb3IgJFxib2xkc3ltYm9se1xTaWdtYX0kLCBpdCBjYW4gYmUgZWFzaWx5IGNvbXB1dGVkIGZyb20gUiB1c2luZyBgTCA9IGNob2woU2lnbWEpYC4gSXQgaXMgdGhlbiBwbG90dGVkIGFzIGJlbG93LiAKCmBgYHtyIENob2xlc2t5LCBlY2hvID0gRiwgZmlnLmFsaWduPSdjZW50ZXInfQojIFVzaW5nIFIgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIENob2xlc2t5IGRlY29tcG9zaXRpb24KTCA8LSBjaG9sKFNpZ21hKQpsZXZlbHBsb3QodChMKSwgeWxpbT1jKDEwMCwxKSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKCiMgRkI6IEF0dGVudGlvbiEhIGNob2woKSBnaXZlcyB3aGF0IGlzIExedCBpbiBvdXIgZXhlcmNpc2Ugc2hlZXQsIGkuZS4gTD1jaG9sKFNpZ21hKSBpcyBhbiB1cHBlciBidXQgTk9UIGxvd2VyIG1hdHJpeCEKYGBgCgoKIyMjIGMpIApTYW1wbGUgdXNpbmcgJFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7TH1cYm9sZHN5bWJvbHt6fSQgdHJhbnNmb3JtcyB0aGUgemVyby1tZWFuLCBzdGFuZGFyZCBub3JtYWwgcmFuZG9tIHZhcmlhbGVzIHRvIHRoZSByYW5kb20gdmFyaWFibGVzIHdpdGggdGhlIGRlc2lyZWQgY292YXJpYW5jZSBtYXRyaXguIAoKYGBge3IsIHJhbmRvbSBzYW1wbGVzLCBmaWcuYWxpZ249J2NlbnRlcid9CnogPSBybm9ybSgxMDApCnggPSBMICUqJSB6CnBsb3QoeCwgbWFpbiA9ICJSYW5kb20gc2FtcGxlcyBnaXZlbiB0aGUgY292YXJpYW5jZSIpCmBgYAoKCiMjIyBkKSAKVGhlIHByZWNpc2lvbiBtYXRyaXggJFxib2xkc3ltYm9se1F9JCBpcyB0aGUgaW52ZXJzZSBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXggJFxib2xkc3ltYm9se1xTaWdtYX0kLCBpdCBpcyBjb21wdXRlZCB1c2luZyBgUSA9IHNvbHZlKFNpZ21hKWAgaW4gUi4gVGhlIHRocmVlIG1hdHJpY2VzIGFyZSB0aGVyZWJ5IGRlcGljdGVkIGFzIGZvbGxvd3MuIFNpbmNlIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBpcyBub3Qgc2luZ3VsYXIsIGdpdmVuIHRoYXQgdGhlIGl0IGJlbG9uZ3MgdG8gdGhlIE1hdGVybiBmYW1pbHksIHRodXMgaXQgaXMgYW5hbHl0aWNhbGx5IGd1YXJhbnRlZWQgdG8gaGF2ZSBwb3NpdGl2ZSBkZWZpbml0ZSBwcm9wZXJ0eS4gVGhlcmVmb3JlLCBib3RoIHByZWNpc2lvbiBtYXRyaXggYW5kIHRoZSBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXggZXhpc3QuIAoKYGBge3IgY29tcCBiZXR3ZWVuIHRocmVlIG1hdHJpY2VzLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQpRIDwtIHNvbHZlKFNpZ21hKQpMUSA8LSBjaG9sKFEpCnBhcihtYXIgPSBjKDQsNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiQ292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoTCwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIlByZWNpc2lvbiBtYXRyaXgiKQpsZXZlbHBsb3QoTFEsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9ICJMb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKQojIGxldmVscGxvdChMUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKYGBgCgoKIyMjIGUpIApTaW1pbGFybHksIHRoZSBleHBlY3RlZCByYW5kb20gc2FtcGxlcyBjYW4gYmUgZ2VuZXJhdGVkIHVzaW5nIHRoZSBpbnZlcnNpb24gb2YgdGhlIGFib3ZlIGZvcm11bGEsIHRodXMgJFxib2xkc3ltYm9se0x9X1FeVFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7en0kCgpgYGB7ciwgc2FtcGxlIGluIGludmVyc2lvbiB3YXksIGZpZy5hbGlnbj0nY2VudGVyJ30KeiA9IHJub3JtKDEwMCkKeCA9IHNvbHZlKHQoTFEpLCB6KQpwbG90KHgsIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKQpgYGAKCiMjIyBmKSAKUGVybXV0ZSAkXGJvbGRzeW1ib2x7eH0kIHRvIG1ha2UgcmFuZG9taXNlIHRoZSBvcmRlcmluZyBvZiB0aGUgZ3JpZCwgdGhlIGFzc2NvY2lhdGVkIGNvdmFyaWFuY2UgbWF0cml4IGNhbiBiZSB0aGVyZWJ5IG1vZGlmaWVkIGluIGEgc3BhcnNlIHdheS4gCgpgYGB7ciwgcGVybXV0YXRpb24sIGZpZy5hbGlnbj0nY2VudGVyJ30Kbl9wZXIgPSAzClNpZ21hX3BlciA8LSBsaXN0KCkKTF9wZXIgPC0gbGlzdCgpClFfcGVyIDwtIGxpc3QoKQpMUV9wZXIgPC0gbGlzdCgpCmZvciAoaSBpbiBjKDE6bl9wZXIpKXsKICBzaXRlczF2X3BlciA8LSBhcnJheShzYW1wbGUoc2l0ZXMxdiwgc2l6ZSA9IG4sIHJlcGxhY2UgPSBGQUxTRSksIGMobiwxKSkKICAjIGRldGVybWluZSB0aGUgZGlzdGFuY2UgbWF0cml4CiAgSF9wZXIgPC0gYWJzKHNpdGVzMXZfcGVyJSoldCh3dyktd3cgJSolIHQoc2l0ZXMxdl9wZXIpKQogICMgRXhwb25lbnRpYWwgY292YXJpYW5jZSBtb2RlbAogIFNpZ21hX3RlbXAgPC0gZXhwKC0wLjEqSF9wZXIpCiAgU2lnbWFfcGVyW1tpXV0gPC0gU2lnbWFfdGVtcAogICMgTCBtYXRyaXgKICBMX3RlbXAgPC0gY2hvbChTaWdtYV90ZW1wKQogIExfcGVyW1tpXV0gPC0gTF90ZW1wCiAgCiAgeiA9IHJub3JtKDEwMCkKICB4X3BlciA9IExfdGVtcCAlKiUgegogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgZ2l2ZW4gdGhlIGNvdmFyaWFuY2UiKSkKICAKICBRX3RlbXAgPC0gc29sdmUoU2lnbWFfdGVtcCkKICBMUV90ZW1wIDwtIGNob2woUV90ZW1wKQogIFFfcGVyW1tpXV0gPC0gUV90ZW1wCiAgTFFfcGVyW1tpXV0gPC0gTFFfdGVtcAogIHogPSBybm9ybSgxMDApCiAgeF9wZXIgPSBzb2x2ZSh0KExRX3RlbXApLCB6KQogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKSkKfQoKCmBgYAoKYGBge3IsIGNvbnQgcGxvdHRpbmcgMSwgZmlnLnNob3cgPSAiaG9sZCIsIG91dC53aWR0aD0iNTAlIn0KaSA9IDEKcGFyKG1hciA9IGMoNCwgNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KExfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIHByZWNpc2lvbiBtYXRyaXgiKSkKbGV2ZWxwbG90KExRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKSkKYGBgCgpgYGB7ciwgY29udCBwbG90dGluZyAyLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQppID0gMgpwYXIobWFyID0gYyg0LCA0LC4xLCAuMSkpCiMgcGFyKG1mcm93PWMoMSwzKSwgbWFyPWMoNCw0LDQsMSksIG9tYT1jKDAuNSwwLjUsMC41LDApKQpsZXZlbHBsb3QoU2lnbWFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksICJQZXJtdXRlZCBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoTF9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgcHJlY2lzaW9uIG1hdHJpeCIpKQpsZXZlbHBsb3QoTFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgcHJlY2lzaW9uIG1hdHJpeCIpKQpgYGAKCmBgYHtyLCBjb250IHBsb3R0aW5nIDMsIGZpZy5zaG93ID0gImhvbGQiLCBvdXQud2lkdGg9IjUwJSJ9CmkgPSAzCnBhcihtYXIgPSBjKDQsIDQsLjEsIC4xKSkKIyBwYXIobWZyb3c9YygxLDMpLCBtYXI9Yyg0LDQsNCwxKSwgb21hPWMoMC41LDAuNSwwLjUsMCkpCmxldmVscGxvdChTaWdtYV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwgIlBlcm11dGVkIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChMX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBwcmVjaXNpb24gbWF0cml4IikpCmxldmVscGxvdChMUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBwcmVjaXNpb24gbWF0cml4IikpCmBgYAoKCgojIFBhcnQgSUkgR2F1c3NpYW4gcmFuZG9tIGZpZWxkcyBhbmQgS3JpZ2luZwoKVGhlIHB1cnBvc2Ugb2YgdGhpcyBjb21wdXRlciBleGVyY2lzZSBpcyB0byBnaXZlIGFuIGludHJvZHVjdGlvbiB0byBwYXJhbWV0ZXIgZXN0aW1hLSB0aW9uIGFuZCBrcmlnaW5nIGZvciBHYXVzc2lhbiByYW5kb20gZmllbGQgbW9kZWxzIGZvciBzcGF0aWFsIGRhdGEuCgpXZSBhc3N1bWUgdGhlIGZvbGxvd2luZyBvYnNlcnZhdGlvbiBtb2RlbCBvbiB0aGUgdW5pdCBzcXVhcmU6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgeShcYm9sZHN5bWJvbHtzfV9qKSA9IHgoXGJvbGRzeW1ib2x7c31faikgKyBcZXBzaWxvbl9qLCBcIFwgXCAgaiA9IDEsIFxkb3RzLCBOLApcZW5ke2VxdWF0aW9uKn0KCndoZXJlICRcZXBzaWxvbl9qIH4gXG1hdGhvcHtOfSgwLCBcdGF1XjIpJCBhcmUgaW5kZXBlbmRlbnQgbWVhc3VyZW1lbnQgbm9pc2UgdGVybXMuIEZ1cnRoZXIsIGNvbnNpZGVyIGEgTWF0w6lybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uIGZvciB0aGUgR2F1c3NpYW4gcmFuZG9tIGZpZWxkICRcYm9sZHN5bWJvbHt4KHMpfSQ6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgQ292KHgoXGJvbGRzeW1ib2x7c31faSksIHgoXGJvbGRzeW1ib2x7c31faikpID0gXFNpZ21hX3tpLCBqfSA9IFxzaWdtYV4yKDEgKyBccGhpIGgpXGV4cCgtXHBoaSBoKSwKXGVuZHtlcXVhdGlvbip9Cgp3aGVyZSAkaCQgZGVub3RlcyB0aGUgRXVjbGlkZWFuIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBzaXRlcyAkXGJvbGRzeW1ib2x7c31faSQgYW5kICRcYm9sZHN5bWJvbHtzfV9qJC4KCldlIGFzc3VtZSB0aGUgbWVhbiBpbmNyZWFzZXMgd2l0aCBlYXN0IGFuZCBub3J0aCBjb29yZGluYXRlcyBhcyBmb2xsb3dzOiAkXG11X2ogPSBcYWxwaGEoKHNfe2oxfSAtIDAuNSkgKyAoc197ajJ9IC0gMC41KSkkLCBmb3Igc2l0ZSAkXGJvbGRzeW1ib2x7c31faiA9IChzX3tqMX0sIHNfe2oyfSkkIG9uIHRoZSB1bml0IHNxdWFyZS4gCgoqKiogCgojIyAyLjEgU2ltdWxhdGlvbgoKU2ltdWxhdGUgJE4gPSAyMDAkIHJhbmRvbSBzaXRlcyBpbiB0aGUgdW5pdCBzcXVhcmUgYW5kIHBsb3QgdGhlbS4gRm9ybSB0aGUgY292YXJpYW5jZSBtYXRyaXggdXNpbmcgJFxzaWdtYSA9IDEsIFxwaGkgPSAxMCwgXHRhdSA9IDAuMDUkLiBUYWtlIGl0cyBDaG9sZXNreSBkZWNvbXBvc2l0aW9uIGFuZCBzaW11bGF0ZSBkZXBlbmRlbnQgemVyby1tZWFuIEdhdXNzaWFuIGRhdGEgdmFyaWFibGVzLCB0aGVuIGFkZCB0aGUgbWVhbiB1c2luZyAkXGFscGhhID0gMSQuIFBsb3QgeW91ciBvYnNlcnZhdGlvbnMuCgoKVGhlIHRydWUgbWVhbiBvZiB0aGUgZmllbGQgaXMgZXhwcmVzc2VkIGFzIAogICAgXGJlZ2lue2VxdWF0aW9uKn0KICAgICAgICBcbXVfaSA9IFxhbHBoYSgoc197aTF9IC0gMC41KSArIChzX3tpMn0gLSAwLjUpKSA9IC1cYWxwaGEgKyBcYWxwaGEgc197aTF9ICsgXGFscGhhIHNfe2kyfSA9IFx1bmRlcmJyYWNlewogICAgICAgIFxiZWdpbntibWF0cml4fQogICAgICAgIDEgJiBzX3tpMX0gJiBzX3tpMn0gXFwKICAgICAgICBcZW5ke2JtYXRyaXh9fV97XGJvbGRzeW1ib2x7aH1eVChcYm9sZHN5bWJvbHtzfV9pKX0KICAgICAgICBcdW5kZXJicmFjZXsKICAgICAgICBcYmVnaW57Ym1hdHJpeH0KICAgICAgICAtXGFscGhhIFxcCiAgICAgICAgXGFscGhhIFxcCiAgICAgICAgXGFscGhhIAogICAgICAgIFxlbmR7Ym1hdHJpeH19X3tcYm9sZHN5bWJvbHtcYmV0YX19CiAgICBcZW5ke2VxdWF0aW9uKn0KICAgIHdoZXJlICRzX3tpMX0sIHNfe2kyfSQgYXJlIHRoZSBsb2NhdGlvbiBmcm9tIGVhc3QgYW5kIG5vcnRoIGRpcmVjdGlvbiBpbiB0aGUgZ3JpZC4gCgpgYGB7ciBHUCBzaW11bGF0aW9ufQoKTWF0ZXJuX2NvdiA8LSBmdW5jdGlvbihzaWdtYSwgcGhpLCB0KXsKICAgICMgcGFyYW0gc2lnbWE6IHNjYWxpbmcgY29lZgogICAgIyBwYXJhbSBldGE6IHJhbmdlIGNvZWYKICAgICMgcGFyYW0gdDogZGlzdGFuY2UgbWF0cml4CiAgICAjIHJldHVybjogbWF0ZXJuIGNvdmFyaWFuY2UKICAgIHJldHVybihzaWdtYSBeIDIgKiAoMSArIHBoaSAqIHQpICogZXhwKC1waGkgKiB0KSkKfQoKcGxvdGYgPC0gZnVuY3Rpb24odiwgc3RyaW5nKXsKICB2diA8LSB2CiAgZGltKHZ2KSA8LSBjKG4xLCBuMikKICBsZXZlbHBsb3QodnYsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHN0cmluZykKfQoKIyBTZXR1cCB0aGUgZ3JpZApuMSA9IDI1ICMgbnVtYmVyIG9mIGdyaWQgcG9pbnRzIGFsb25nIGVhc3QgZGlyZWN0aW9uCm4yID0gMjUgIyBudW1iZXIgb2YgZ3JpZCBwb2ludHMgYWxvbmcgbm9ydGggZGlyZWN0aW9uCm4gPSBuMSAqIG4yICMgdG90YWwgbnVtYmVyIG9mIGdyaWQgcG9pbnRzCgpkbjEgPSAxL24xCmRuMiA9IDEvbjIKc2l0ZXMxID0gYXJyYXkoc2VxKDAsIDEsIGRuMSksIGMobjEsIDEpKQpzaXRlczIgPSBhcnJheShzZXEoMCwgMSwgZG4yKSwgYyhuMiwgMSkpCiMgc2l0ZXMxID0gYXJyYXkoc2VxKDEsIG4xKSwgYyhuMSwgMSkpCiMgc2l0ZXMyID0gYXJyYXkoc2VxKDEsIG4yKSwgYyhuMiwgMSkpCnd3MSA9IHJlcCgxLCBuMSkKd3cyID0gcmVwKDEsIG4yKQpzaXRlczFtID0gc2l0ZXMxICUqJSB0KHd3MSkgIyBzaXRlczFtIGlzIHRoZSBtYXRyaXggdmVyc2lvbiBvZiBzaXRlczEKc2l0ZXMybSA9IHd3MiAlKiUgdChzaXRlczIpCgpzaXRlczF2ID0gbWF0cml4KHNpdGVzMW0sIG5yb3cgPSBuLCBuY29sID0gMSkKc2l0ZXMydiA9IG1hdHJpeChzaXRlczJtLCBucm93ID0gbiwgbmNvbCA9IDEpCgpwbG90KHNpdGVzMXYsIHNpdGVzMnYpCgojIENvbXB1dGUgdGhlIGRpc3RhbmNlIG1hdHJpeApkZEUgPSBzaXRlczF2ICUqJSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gMSwgbmNvbCA9IG4pIC0gbWF0cml4KHJlcCgxLCBuKSwgbnJvdyA9IG4sIG5jb2wgPSAxKSAlKiUgdChzaXRlczF2KQpkZDJFID0gZGRFICogZGRFCmRkTiA9IHNpdGVzMnYgJSolIG1hdHJpeChyZXAoMSwgbiksIG5yb3cgPSAxLCBuY29sID0gbikgLSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gbiwgbmNvbCA9IDEpICUqJSB0KHNpdGVzMnYpCmRkMk4gPSBkZE4gKiBkZE4KdCA9IHNxcnQoZGQyRSArIGRkMk4pCmxldmVscGxvdCh0LCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiRGlzdGFuY2UgbWF0cml4IikKCiMgU2ltdWxhdGUgdGhlIGluaXRpYWwgcmFuZG9tIGZpZWxkCmFscGhhID0gMS4wICMgYmV0YSBhcyBpbiByZWdyZXNzaW9uIG1vZGVsCnNpZ21hID0gMS4wICAjIHNjYWxpbmcgY29lZiBpbiBtYXRlcm4ga2VybmVsCnBoaSA9IDEwICMgcmFuZ2UgY29lZiBpbiBtYXRlcm4ga2VybmVsCiMgZXRhID0gMTAgIyByYW5nZSBjb2VmIGluIG1hdGVybiBrZXJuZWwKdGF1ID0gLjA1ICMgaWlkIG5vaXNlCgpiZXRhMSA9IC1hbHBoYQpiZXRhMiA9IGFscGhhCmJldGEzID0gYWxwaGEKCkJFVEFfVFJVRSA9IG1hdHJpeChjKGJldGExLCBiZXRhMiwgYmV0YTMpLCBucm93ID0gMywgbmNvbCA9IDEpClRIRVRBX1RSVUUgPSBtYXRyaXgoYyhzaWdtYSwgcGhpLCB0YXUpLCBucm93ID0gMywgbmNvbCA9IDEpCgpTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkgICMgbWF0ZXJuIGNvdmFyaWFuY2UKCkwgPSBjaG9sKFNpZ21hKSAjIGxvd2VyIEwKeCA9IHQoTCkgJSolIHJub3JtKG4pICMgc2FtcGxlIGZyb20gemVybyBtZWFuIHJhbmRvbSB2YXJpYWJsZXMKCkggPSBhcnJheShjKHJlcCgxLCBuKSwgc2l0ZXMxdiwgc2l0ZXMydiksIGRpbSA9IGMobiwgMykpICMgZGVzaWduIG1hdHJpeAptdV9wcmlvciA9IEggJSolIEJFVEFfVFJVRQpwbG90ZihtdV9wcmlvciwgInByaW9yIG1lYW4iKQptdV9yZWFsID0gbXVfcHJpb3IgKyB4CnBsb3RmKG11X3JlYWwsICJyZWFsaXNhdGlvbiBvZiB0aGUgZ3JmIikKCiMgc2FtcGxpbmcgZnJvbSByZWFsaXNhdGlvbnMKTSA9IDIwMApGbWF0cml4ID0gbWF0cml4KDAsIE0sIG4pCmluZCA9IHNhbXBsZShuLCBzaXplID0gTSwgcmVwbGFjZSA9IEZBTFNFKQpmb3IgKGkgaW4gYygxOk0pKXsKICBGbWF0cml4W2ksIGluZFtpXV0gPSBUUlVFCn0KRyA9IEZtYXRyaXggJSolIEgKeV9zYW1wbGVkID0gRm1hdHJpeCAlKiUgbXVfcmVhbCArIHRhdSAqIHJub3JtKE0sIDEpCnhfaW5kID0gc2l0ZXMxdltpbmRdCnlfaW5kID0gc2l0ZXMydltpbmRdCgpwbG90KHhfaW5kLCB5X2luZCwgY2V4ID0gYWJzKHlfc2FtcGxlZCksIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgaW4gdGhlIGZpZWxkLCBjaXJjbGUgc2l6ZSBpbmRpY2F0ZXMgdGhlIHJlbGF0aXZlIHZhbHVlIikKCmBgYAoKKioqCgojIyAyLjIgUGFyYW10ZXIgZXN0aW1hdGlvbgoKV2Ugd2lsbCBub3cgdXNlIHRoZSBzaW11bGF0ZWQgZGF0YSB0byBlc3RpbWF0ZSB0aGUgbW9kZWwgcGFyYW1ldGVycyAkXGFscGhhLCBcc2lnbWFeMiwgXHRhdV4yLCBccGhpJCB1c2luZyBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbi4gSXRlcmF0ZSBiZXR3ZWVuIHRoZSB1cGRhdGUgZm9yIHRoZSBtZWFuIHBhcmFtZXRlciwgYW5kIHVwZGF0aW5nIHRoZSBjb3ZhcmlhbmNlIHBhcmFtZXRlcnMuIE1vbml0b3IgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gYXQgZWFjaCBzdGVwIG9mIHRoZSBhbGdvcml0aG0gdG8gY2hlY2sgY29udmVyZ2VuY2UuCgpUaGUgbWVhbiBvZiB0aGUgZmllbGQgaXMgbW9kZWxsZWQgYnkgJHAoXGJvbGRzeW1ib2x7eH0pJCBhbmQgdGhlIGltcGVyZmVjdCBpbmZvcm1hdGlvbiAkXGJvbGRzeW1ib2x7eX0gPSAoeV8xLCBcZG90cywgeV9tKSQgY29uZGl0aW9uYWwgb24gJFxib2xkc3ltYm9se3h9JCBjYW4gYmUgbW9kZWxsZWQgYnkgJHAoXGJvbGRzeW1ib2x7eX18XGJvbGRzeW1ib2x7eH0pJCwgd2hpY2ggY2FuIGJlIGV4cHJlc3NlZCBhcyBmb2xsb3dzOgogICAgXGJlZ2lue2VxdWF0aW9uKn0KICAgICAgICBwKFxib2xkc3ltYm9se3h9KSA9IFxtYXRob3B7Tn0oXGJvbGRzeW1ib2x7SH1cYmV0YSwgXGJvbGRzeW1ib2x7XFNpZ21hfSksIFxxdWFkIHAoXGJvbGRzeW1ib2x7eX18XGJvbGRzeW1ib2x7eH0pID0gXG1hdGhvcHtOfShcYm9sZHN5bWJvbHtGeH0sIFxib2xkc3ltYm9se1R9KQogICAgXGVuZHtlcXVhdGlvbip9CiAgICBUaGVyZWZvcmUsIHRoZSBtYXJnaW5hbCBsaWtlbGlob29kIG9mIHRoZSBkYXRhIGlzIAogICAgXGJlZ2lue2VxdWF0aW9uKn0KICAgICAgICBwKFxib2xkc3ltYm9se3l9KSA9IFxtYXRob3B7Tn0oXGJvbGRzeW1ib2x7R1xiZXRhfSwgXGJvbGRzeW1ib2x7Q30pLCBccXVhZCBcYm9sZHN5bWJvbHtHfSA9IFxib2xkc3ltYm9se0ZIfSwgXHF1YWQgXGJvbGRzeW1ib2x7Q30gPSBcYm9sZHN5bWJvbHtGXFNpZ21hIEZeVH0gKyBcYm9sZHN5bWJvbHtUfQogICAgXGVuZHtlcXVhdGlvbip9CiAgICBUaGUgbG9nLWxpa2VsaWhvb2QgYXMgYSBmdW5jdGlvbiBvZiAkXGJldGEkIGFuZCB1bmtub3duIGZpeGVkIG51aXNhbmNlIHBhcmFtZXRlcnMgJFxib2xkc3ltYm9se1x0aGV0YX0kIGluIHRoZSBwcmlvciBjb3ZhcmlhbmNlIG1hdHJpeCAkXGJvbGRzeW1ib2x7XFNpZ21hfSA9IFxib2xkc3ltYm9se1xTaWdtYShcYm9sZHN5bWJvbHtcdGhldGF9KX0kLCBhbmQvb3IgdGhlIGxpa2VsaWhvb2Qgbm9pc2UgbWF0cml4ICRcYm9sZHN5bWJvbHtUfSA9IFxib2xkc3ltYm9se1R9KFxib2xkc3ltYm9se1x0aGV0YX0pJCBiZWNvbWVzCiAgICBcYmVnaW57ZXF1YXRpb24qfQogICAgICAgIGwoXGJvbGRzeW1ib2x7XHRoZXRhfSwgXGJvbGRzeW1ib2x7XGJldGF9KSA9IC1cZnJhY3ttfXsyfSBcbG9nKDJccGkpIC0gXGZyYWN7MX17Mn1cbG9nfFxib2xkc3ltYm9se0N9fCAtIFxmcmFjezF9ezJ9KFxib2xkc3ltYm9se3l9IC0gXGJvbGRzeW1ib2x7R31cYm9sZHN5bWJvbHtcYmV0YX0pXlRcYm9sZHN5bWJvbHtDfV57LTF9KFxib2xkc3ltYm9se3l9IC0gXGJvbGRzeW1ib2x7R1xiZXRhfSkKICAgIFxlbmR7ZXF1YXRpb24qfQoKIFRoZSBNTEVzIG9mICRcYm9sZHN5bWJvbHtcYmV0YX0kIGFuZCAkXGJvbGRzeW1ib2x7XHRoZXRhfSQgYXJlIG9idGFpbmVkIGJ5CiAgICBcYmVnaW57ZXF1YXRpb24qfQogICAgICAgIChcaGF0e1xib2xkc3ltYm9se1xiZXRhfX0sIFxoYXR7XGJvbGRzeW1ib2x7XHRoZXRhfX0pID0gXHVuZGVyc2V0e1xib2xkc3ltYm9se1xiZXRhfSwgXGJvbGRzeW1ib2x7XHRoZXRhfX17XGFyZ1xtYXh9XHtsKFxib2xkc3ltYm9se1xiZXRhLCBcdGhldGF9KVx9CiAgICBcZW5ke2VxdWF0aW9uKn0KICAgIEZvciBmaXhlZCAkXGJvbGRzeW1ib2x7XHRoZXRhfSQsIHRoZSBNTEVzIG9mICRcYm9sZHN5bWJvbHtcYmV0YX0kIGNhbiBiZSBkZXRlcm1pbmVkIGFuYWx5dGljYWxseS4KICAgIFxiZWdpbntlcXVhdGlvbip9CiAgICAgICAgXGZyYWN7ZGx9e2RcYm9sZHN5bWJvbHtcYmV0YX19ID0gXGJvbGRzeW1ib2x7R31eVFxib2xkc3ltYm9se0N9XnstMX1cYm9sZHN5bWJvbHt5fSAtIFxib2xkc3ltYm9se0d9XlRcYm9sZHN5bWJvbHtDfV57LTF9XGJvbGRzeW1ib2x7R31cYm9sZHN5bWJvbHtcYmV0YX0gPSBcYm9sZHN5bWJvbHswfSwgXHF1YWQgXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19ID0gKFxib2xkc3ltYm9se0d9XlRcYm9sZHN5bWJvbHtDfV57LTF9XGJvbGRzeW1ib2x7R30pXnstMX1cYm9sZHN5bWJvbHtHfV5UXGJvbGRzeW1ib2x7Q31eey0xfVxib2xkc3ltYm9se3l9CiAgICBcZW5ke2VxdWF0aW9uKn0KICAgIFdoZXJlYXMgZm9yIGZpeGVkICRcYm9sZHN5bWJvbHtcYmV0YX0kLCB0aGUgTUxFIG9mIG51aXNhbmNlIHBhcmFtZXRlcnMgJFxib2xkc3ltYm9se1x0aGV0YX0kIGNhbiBiZSBvYnRhaW5lZCBieSBudW1lcmljYWwgbWF4aW1pemF0aW9uLiBMZXQgJFxib2xkc3ltYm9se3p9ID0gXGJvbGRzeW1ib2x7eX0gLSBcYm9sZHN5bWJvbHtHXGJldGF9JCwgYW5kICRcYm9sZHN5bWJvbHtRfSA9IFxib2xkc3ltYm9se0N9XnstMX0kLiBGb3IgZWFjaCBjb21wb25lbnQgb2YgJFxib2xkc3ltYm9se1x0aGV0YX1fciQsICRyID0gMSwgXGRvdHMsIGQkLCBpbiB0aGlzIGNhc2UsICRcdGhldGEkIGhhcyAzIGNvbXBvbmVudHMgKCRcc2lnbWFeMiwgXGV0YSwgXHRhdV4yJCkuIFRoZSBzY29yZSBvZiB0aGUgbG9nLWxpa2VsaWhvb2QgYmVjb21lcwogICAgXGJlZ2lue2VxdWF0aW9uKn0KICAgICAgICBcZnJhY3tkbH17ZFx0aGV0YV9yfSA9IC1cZnJhY3sxfXsyfVx0ZXh0e3RyYWNlfShcYm9sZHN5bWJvbHtRfVxmcmFje2RcYm9sZHN5bWJvbHtDfX17ZFx0aGV0YV9yfSkgKyBcZnJhY3sxfXsyfVxib2xkc3ltYm9se3p9XlRcYm9sZHN5bWJvbHtRfVxmcmFje2RcYm9sZHN5bWJvbHtDfX17ZFx0aGV0YV9yfVxib2xkc3ltYm9se1F6fQogICAgXGVuZHtlcXVhdGlvbip9CgoKIFRoZSBhYm92ZSBtZW50aW9uZWQgc2NvcmUgY2FuIGJlIHNvbHZlZCBpdGVyYXRpdmVseSB1c2luZyBGaXNoZXIgc2NvcmluZyBhbGdvcml0aG0uIFRvIGFjaGlldmUgdGhlIG51bWVyaWNhbCBzdGFiaWxpdHksIHRoZSBleHBlY3RlZCBIZXNzaWFuIGlzIGFwcGxpZWQsIHdoaWNoIGlzIAogICAgXGJlZ2lue2VxdWF0aW9uKn0KICAgICAgICBcbWF0aG9we0V9KFxmcmFje2ReMmx9e2RcdGhldGFfcmRcdGhldGFfe1xiYXJ7cn19fSkgPSAtXGZyYWN7MX17Mn1cdGV4dHt0cmFjZX0oXGJvbGRzeW1ib2x7UX1cZnJhY3tkXGJvbGRzeW1ib2x7Q319e2RcdGhldGFfe1xiYXJ7cn19fVxib2xkc3ltYm9se1F9XGZyYWN7ZFxib2xkc3ltYm9se0N9fXtkXHRoZXRhX3J9KQogICAgXGVuZHtlcXVhdGlvbip9CiAgICAKXGJlZ2lue2FsZ29yaXRobX1bSF0KICAgICBcS3dEYXRhe2luaXRpYWwgJFxiZXRhXzAkLCAkXHRoZXRhXzAkfQogICAgIFxLd1Jlc3VsdHtDb252ZXJnZWQgJFxoYXR7XGJldGF9JCwgJFxoYXR7XHRoZXRhfSR9CiAgICAgXFdoaWxle25vdCBjb252ZXJnZWR9ewogICAgICAkXGJvbGRzeW1ib2x7Q30gPSBcYm9sZHN5bWJvbHtDfShcYm9sZHN5bWJvbHtcdGhldGF9XmIpJFw7CiAgICAgICRcYm9sZHN5bWJvbHtcYmV0YX1ee2IrMX0gPSBbXGJvbGRzeW1ib2x7R31eVFxib2xkc3ltYm9se0N9XnstMX1cYm9sZHN5bWJvbHtHfV1eey0xfVxib2xkc3ltYm9se0d9XlRcYm9sZHN5bWJvbHtDfV57LTF9XGJvbGRzeW1ib2x7eX0kXDsKICAgICAgJFxib2xkc3ltYm9se3p9ID0gXGJvbGRzeW1ib2x7eX0gLSBcYm9sZHN5bWJvbHtHfVxib2xkc3ltYm9se1xiZXRhfV57YiArIDF9JFw7CiAgICAgICRcYm9sZHN5bWJvbHtRfSA9IFxib2xkc3ltYm9se0N9XnstMX0kIFw7CiAgICAgICRcYm9sZHN5bWJvbHtDfV4qX3IgPSBcZnJhY3tkXGJvbGRzeW1ib2x7Q30oXGJvbGRzeW1ib2x7XHRoZXRhfV5iKX17ZFx0aGV0YV9yfSwgXHF1YWQgciA9IDEsIFxkb3RzLCBkJCBcOyAKICAgICAgJHVfciA9IFxmcmFje2RsfXtkXHRoZXRhX3J9ID0gLVxmcmFjezF9ezJ9XHRleHR7dHJhY2V9KFxib2xkc3ltYm9se1F9XGJvbGRzeW1ib2x7Q31fcl4qKSArIFxmcmFjezF9ezJ9XGJvbGRzeW1ib2x7en1eVFxib2xkc3ltYm9se1F9XGJvbGRzeW1ib2x7Q31fcl4qXGJvbGRzeW1ib2x7UXp9JFw7CiAgICAgICRcYm9sZHN5bWJvbHtWfV97clxiYXJ7cn19PVxtYXRob3B7RX0oXGZyYWN7ZF4ybH17ZFx0aGV0YV9yZFx0aGV0YV97XGJhcntyfX19KSA9IC1cZnJhY3sxfXsyfVx0ZXh0e3RyYWNlfShcYm9sZHN5bWJvbHtRfVxib2xkc3ltYm9se0N9X3JeKlxib2xkc3ltYm9se1F9XGJvbGRzeW1ib2x7Q31fe1xiYXJ7cn19XiopJFw7CiAgICAgICRcYm9sZHN5bWJvbHtcdGhldGF9XntiICsgMX0gPSBcYm9sZHN5bWJvbHtcdGhldGF9XmIgKyBcYm9sZHN5bWJvbHtWfV57LTF9XGJvbGRzeW1ib2x7dX0kXDsKICAgICAgJGIgPSBiICsgMSQKICAgICAgfQogICAgJSAgXGNhcHRpb257SG93IHRvIHdyaXRlIGFsZ29yaXRobXN9CiAgICBcZW5ke2FsZ29yaXRobX0KICAgIApgYGB7ciwgcGFyYW1ldGVyIGVzdGltYXRpb259CiMlJQpDX21hdHJpeCA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkKICBDID0gRm1hdHJpeCAlKiUgU2lnbWEgJSolIHQoRm1hdHJpeCkgKyBkaWFnKE0pICogdGF1XjIKICByZXR1cm4oQykKfQoKCmRDX2RzaWdtYSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgIyBzaWdtYSA9IHRoZXRhJHNpZ21hCiAgIyBwaGkgPSB0aGV0YSRwaGkKICAjIHRhdSA9IHRoZXRhJHRhdQogIHNpZ21hID0gdGhldGFbMV0KICBwaGkgPSB0aGV0YVsyXQogIHRhdSA9IHRoZXRhWzNdCiAgS20gPSBNYXRlcm5fY292KDEuMCwgcGhpLCB0KSAjIHQgaGVyZSBpcyB0aGUgZGlzdGFuY2UgbWF0cml4LCBIIGlzIHRoZSBkZXNpZ24gbWF0cml4LCBzaW1pbGFyIHRvIFgKICBkQ19kc2dtID0gRm1hdHJpeCAlKiUgS20gJSolIHQoRm1hdHJpeCkKICByZXR1cm4oZENfZHNnbSkKfQoKZENfZHBoaSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBLbiA9IHNpZ21hIF4gMiAqICgtcGhpICogdCkgKiBleHAoLXBoaSAqIHQpCiAgcmV0dXJuKEZtYXRyaXggJSolIEtuICUqJSB0KEZtYXRyaXgpKQp9CgpkQ19kdGF1IDwtIGZ1bmN0aW9uKHRoZXRhKXsKICByZXR1cm4oZGlhZyhNKSkKfQoKIyBVc2UgZmlzaGVyIHNjb3JpbmcgdG8gZmluZCBNTEUgcGFyYW1ldGVycwojIGJldGEgPSBucC56ZXJvcyhbMywgMV0pCmJldGEgPSBtYXRyaXgoYygtMi4xLCAzLjEsIC45KSwgbnJvdyA9IDMsIG5jb2wgPSAxKQp0aGV0YSA9IHJiaW5kKC4yNDUsIDkuMywgLjAwMykKTUFYX0lURVIgPSA1Ck5vX2l0ZXIgPSAwCmVwc2lsb24gPSAxMApCZXRhID0gbWF0cml4KDAsIG5yb3cgPSBNQVhfSVRFUiwgbmNvbCA9IDMpCkxpa2VsaWhvb2QgPSBtYXRyaXgoMCwgbnJvdyA9IE1BWF9JVEVSLCBuY29sID0gMSkKCndoaWxlIChOb19pdGVyIDwgTUFYX0lURVIgJiBlcHNpbG9uID4gLjAwMDEpewogICAgQyA9IENfbWF0cml4KHRoZXRhKQogICAgYmV0YSA9IHNvbHZlKHQoRykgJSolIHNvbHZlKEMsIEcpLCB0KEcpICUqJSBzb2x2ZShDLCB5X3NhbXBsZWQpKQogICAgIyBiZXRhID0gbnAubGluYWxnLnNvbHZlKG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCBHKSksIG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCB5X3NhbXBsZWQpKSkKICAgIEJldGFbTm9faXRlciwgXSA9IHQoYmV0YSkKICAgIHogPSB5X3NhbXBsZWQgLSBHICUqJSBiZXRhCiAgICBsaWsgPSAtTS8yICogbG9nKDIgKiBwaSkgLSAxLzIgKiBsb2coZGV0KEMpKSAtICAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCB6KSAjIG90aGVyd2lzZSwgaXQgYmVjb21lcyBpbmYKICAgIExpa2VsaWhvb2RbTm9faXRlciwgXSA9IGxpawoKICAgICMgRmluZCBkQyovZHRoZXRhCiAgICBkQ19kU2dtID0gZENfZHNpZ21hKHRoZXRhKQogICAgZENfZFBoaSA9IGRDX2RwaGkodGhldGEpCiAgICBkQ19kVGF1ID0gZENfZHRhdSh0aGV0YSkKCiAgICB1X3NpZ21hID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RTZ20pKSkgKyAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCBkQ19kU2dtICUqJSBzb2x2ZShDLCB6KSkKICAgIHVfZXRhID0gLTEgLyAyICogc3VtKGRpYWcoc29sdmUoQywgZENfZFBoaSkpKSArIDEgLyAyICogdCh6KSAlKiUgc29sdmUoQywgZENfZFBoaSAlKiUgc29sdmUoQywgeikpCiAgICB1X3RhdSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RUYXUpKSkgKyAxIC8gMiAqIHQoeikgJSolIHNvbHZlKEMsIGRDX2RUYXUgJSolIHNvbHZlKEMsIHopKQoKICAgIHUgPSByYmluZCh1X3NpZ21hLCB1X2V0YSwgdV90YXUpCgogICAgVjExID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYxMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYxMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYyMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYyMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYyMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYzMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYzMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYzMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKCiAgICBWID0gbWF0cml4KGMoVjExLCBWMTIsIFYxMywgVjIxLCBWMjIsIFYyMywgVjMxLCBWMzIsIFYzMyksIG5yb3cgPSAzLCBuY29sID0gMykKICAgICMgcHJpbnQobGlrKQogICAgIyBwcmludChOb19pdGVyKQogICAgdGhldGFfbmV3ID0gdGhldGEgLSBzb2x2ZShWLCB1KSAgIyBoZXJlIGl0IGlzIG1pbnVzLCBidXQgaW4gdGhlIGJvb2ssIGl0IHNheXMgcGx1cywgbmVlZHMgdG8gYmUgcmVjaGVja2VkCiAgICBlcHNpbG9uID0gbm9ybSh0aGV0YV9uZXcgLSB0aGV0YSwgdHlwZSA9ICIyIikgLyBub3JtKGJldGEsIHR5cGUgPSAiMiIpCiAgICB0aGV0YSA9IHRoZXRhX25ldwogICAgcHJpbnQocGFzdGUoZXBzaWxvbiAsICIgLCBpdGVyIG5vIGlzICIsIE5vX2l0ZXIpKQogICAgTm9faXRlciA9IE5vX2l0ZXIgKyAxCn0KIyBwcmludChiZXRhKQojIHByaW50KEJFVEFfVFJVRSkKIyBwcmludCh0aGV0YSkKIyBwcmludChUSEVUQV9UUlVFKQoKcGxvdChjKDE6Tm9faXRlciksIExpa2VsaWhvb2QsIG1haW4gPSAibGlrZWxpaG9vZCBmdW5jdGlvbiIpCgojIGFscGhhaCA9IChzdW0obnAuYWJzKGJldGEpKSAvIDMpLnNxdWVlemUoKQp0aGV0YWggPSB0aGV0YQpzaWdtYWggPSB0aGV0YVsxXQpwaGloID0gdGhldGFbMl0KdGF1aCA9IHRoZXRhWzNdCmJldGFoID0gYmV0YQpiZXRhMSA9IGJldGFbMV0KYmV0YTIgPSBiZXRhWzJdCmJldGEzID0gYmV0YVszXQoKIyBwcmludCgnRXN0aW1hdGVkIHNpZ21hIGlzICcsIHNpZ21haCwgIlxuRXN0aW1hdGVkIGV0YSBpcyAiLCBldGFoLCBcCiMgICAgICAgIlxuRXN0aW1hdGVkIHRhdSBpcyAiLCB0YXVoLCAiXG5Fc3RpbWF0ZWQgYWxwaGEgaXMgIiwgYWxwaGFoKQpwcmludChjYXQoIlxuRXN0aW1hdGVkIHNpZ21hIGlzICIsIHJvdW5kKHNpZ21haCwgZGlnaXRzID0gMyksICI7IFRydWUgc2lnbWEgaXMgIiwgVEhFVEFfVFJVRVsxXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBwaGkgaXMgIiwgcm91bmQocGhpaCwgZGlnaXRzID0gMiksICI7IFRydWUgcGhpIGlzICIsIFRIRVRBX1RSVUVbMl0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgdGF1IGlzICIsIHJvdW5kKHRhdWgsIGRpZ2l0cyA9IDUpLCAiOyBUcnVlIHRhdSBpcyAiLCBUSEVUQV9UUlVFWzNdLCAKICAgICAgICAgICAgIlxuRXN0aW1hdGVkIGJldGExIGlzICIsIHJvdW5kKGJldGExLCBkaWdpdHMgPSAyKSwgIjsgVHJ1ZSBiZXRhMSBpcyAiLCBCRVRBX1RSVUVbMV0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgYmV0YTIgaXMgIiwgcm91bmQoYmV0YTIsIGRpZ2l0cyA9IDIpLCAiOyBUcnVlIGJldGEyIGlzICIsIEJFVEFfVFJVRVsyXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBiZXRhMyBpcyAiLCByb3VuZChiZXRhMywgZGlnaXRzID0gMiksICI7IFRydWUgYmV0YTMgaXMgIiwgQkVUQV9UUlVFWzNdKSkKCgpgYGAKCgoqKiogCgojIyAyLjMgS3JpZ2luZwoKV2Ugd2lsbCBub3cgdXNlIHRoZSBlc3RpbWF0ZWQgbW9kZWwgcGFyYW1ldGVycyB0byBwZXJmb3JtIGtyaWdpbmcgcHJlZGljdGlvbi4gUHJlZGljdCB2YXJpYWJsZXMgJHgocykkLCB3aGVyZSBwcmVkaWN0aW9ucyBzaXRlcyBsaWUgb24gYSByZWd1bGFyIGdyaWQgb2Ygc2l6ZSAyNXgyNSBmb3IgdGhlIHVuaXQgc3F1YXJlLiBWaXN1YWxpemUgdGhlIEtyaWdpbmcgc3VyZmFjZSBhbmQgdGhlIHByZWRpY3Rpb24gc3RhbmRhcmQgZXJyb3IuIENvbXBhcmUgd2l0aCB0aGUgdHJ1ZSBmaWVsZC4KCmBgYHtyLCBrcmlnaW5nfQpTaWdtYWggPSBNYXRlcm5fY292KHNpZ21haCwgcGhpaCwgdCkgIyBlc3RpbWF0ZWQgY292YXJpYW5jZSBtYXRyaXgKTGggPSBjaG9sKFNpZ21haCkKbWggPSBIICUqJSBiZXRhaCArIExoICUqJSBybm9ybShuKQpDaCA9IENfbWF0cml4KHRoZXRhaCkKeHAgPSBtaCArIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQywgKHlfc2FtcGxlZCAtIEZtYXRyaXggJSolIG1oKSkKcGxvdGYoeHAsICJwb3N0ZXJpb3IgbWVhbiIpClNpZ21hcCA9IFNpZ21haCAtIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQ2gsIEZtYXRyaXggJSolIFNpZ21haCkKIyBwbG90ZihTaWdtYXAsICJwb3N0ZXJpb3IgY292YXJpYW5jZSIpCmVzdGQgPSBzcXJ0KGRpYWcoU2lnbWFwKSkKcGxvdGYoZXN0ZCwgInBvc3RlcmlvciBzdGQiKQpNU0UgPSBzcXJ0KHN1bShhYnMoeHAgLSBtdV9yZWFsKSAqKiAyKSAvIG4pCnByaW50KHBhc3RlKCJUaGUgcHJlZGljdGlvbiBlcnJvciBpcyAiLCBNU0UpKQpgYGAKCioqKgoKIyBQYXJ0IElJSSBJbnRlZ3JhdGVkIG5lc3RlZCBMYXBsYWNlIEFwcHJveGltYXRpb25zIChJTkxBKQoKIyMgMy4xIFNpbXBsZSBMaW5lYXIgUmVncmVzc2lvbgoKSW4gdGhlIGxhc3QgcGFydCBvZiB0aGlzIGV4ZXJjaXNlIHdlIGV4cGxvcmUgdGhlIFItSU5MQSBwYWNrYWdlLgoKYGBge3IgSU5MQTEsIGVjaG89RkFMU0V9CiMgMSBMb2FkIFItSU5MQSBwYWNrYWdlCmxpYnJhcnkoSU5MQSkKCiMgMiBMb2FkIGFuZCBzYXZlIFNraVB1bXAtZGF0YXNldApza2lEYXRhID0gcmVhZC50YWJsZSgiU2tpSnVtcC50eHQiLCBoZWFkZXI9VFJVRSkKYGBgCgpUaGUgc2tpIGp1bXBpbmcgZGF0YSBzZXQgY29udGFpbnMgMjYgb2JzZXJ2YXRpb25zIG9mIG1lYXN1cmVkIGxlbmd0aHMgaW4gc2tpIGp1bXBpbmcgY29tcGV0aXRpb25zIChpbiBtZXRlcnMpIGJldHdlZW4gMTk2MSBhbmQgMjAxMS4gCgpgYGB7ciBJTkxBMiwgZWNobz1GQUxTRSwgZmlnLmNhcD0iXFxsYWJlbHtmaWc6c2tpRGF0YX1WaXN1YWxpc2F0aW9uIG9mIHRoZSBza2kganVtcGluZyBkYXRhIHNldCJ9CiMgMyBWaXN1YWxpc2F0aW9uCnBsb3Qoc2tpRGF0YSRZZWFyLCBza2lEYXRhJExlbmd0aCwKICAgICB4bGFiPSJ5ZWFyIiwgeWxhYj0ibGVuZ3RoIiwKICAgICBtYWluPSJTa2kganVtcGluZyBkYXRhIikKYGBgCgpJbiBGaWd1cmUgXHJlZntmaWc6c2tpRGF0YX0gd2Ugb2JzZXJ2ZSBhIGNsZWFyIChhbG1vc3QgbGluZWFyKSB0cmVuZCBpbiB0aGUgbWVhc3VyZWQganVtcGluZyBsZW5ndGhzIHRvIGluY3JlYXNlIHdpdGggdGhlIHllYXJzLgoKVGhlcmVmb3JlLCB3ZSB1c2UgbGluZWFyIGFwcHJvYWNoIGZvciB0aGUgc3RhdGlzdGljYWwgbW9kZWxsaW5nIG9mIHRoaXMgZGF0YSwgd2hlcmUgdGhlIHllYXJzICR4X2kkIGFyZSB0aGUgY292YXJpYXRlcyBhbmQgdGhlIGxlbmd0aHMgJHlfaSQgYXJlIHRoZSByZXNwb25zZXMgZm9yICRpPTEsXGRvdHMsMjYkOgpcYmVnaW57ZXF1YXRpb24qfQpcbWF0aGJie0V9W3lfaV0gPSBcbXUgKyBcYmV0YSB4X2ksXHF1YWQgXG1hdGhiYntWYXJ9W3lfaV09XHRhdV57LTF9LgpcZW5ke2VxdWF0aW9uKn0KClRoaXMgY2FuIGJlIHBvc2VkIGFzIGEgbGF0ZW50IEdhdXNzaWFuIG1vZGVsIHN1aXRlZCBmb3IgdGhlIElOTEEgZnJhbWV3b3JrLgoKMS4gICAgVGhlIHJlc3BvbnNlIGRlcGVuZHMgb24gdGhlIGxpbmVhciBwcmVkaWN0b3JzICRcZXRhJCBhcyAkeXx4LFx0aGV0YSA9IFxQaSBccGkoeV9pfFxldGFfaSxcdGF1KSQgd2hlcmUgJFxwaSh5X2l8XGV0YV9pLFx0YXUpXHNpbVxtYXRoY2Fse059KFxldGFfaSxcdGF1XnstMn0pJCAKMi4gICAgVGhlIHBhcmFtZXRlciBvZiB0aGUgbGluZWFyIHByZWRpY3RvciAkZXRhX2k9XG11K3hfaVxiZXRhJCBhcmUgaW5kZXBlbmRlbnQgR2F1c3NpYW4gd2l0aCBzb21lIHZhcmlhbmNlIGFuZCBtZWFuIHplcm8uIAozLiAgICBUaGUgaHlwZXJwYXJhbWV0ZXIgJFx0YXUkIGlzIG9ubHkgb25lLWRpbWVuc2lvbmFsLiAKCmBgYHtyIElOTEEzLCBlY2hvPUZBTFNFLCBmaWcud2lkdGg9MTIsIGZpZy5oZWlnaHQ9NCwgZmlnLmNhcD0iXFxsYWJlbHtmaWc6SU5MQX1Qb3N0ZXJpb3IgbWFyZ2luYWxzIGZvciBzZWxlY3RlZCBlZmZlY3RzIn0KIyA0IExpbmVhciByZWdyZXNzaW9uIHVzaW5nIFItSU5MQQpyZXMgPSBpbmxhKExlbmd0aCB+IFllYXIsIGRhdGE9c2tpRGF0YSkKCiMgUG9zdCBwcm9jZXNzaW5nCnN1bW1hcnkocmVzKQoKcGFyKG1mcm93PWMoMSwzKSkKCnBsb3QoaW5sYS5zbWFyZ2luYWwocmVzJG1hcmdpbmFscy5maXhlZFtbMV1dKSwKICAgICB4bGFiPSJJbnRlcmNlcHQiLCB5bGFiPSJkZW5zaXR5IiwKICAgICBtYWluPSJQb3N0ZXJpb3IgbWFyZ2luYWwgZm9yIGZpeGVkIGVmZmVjdCIpCgpwbG90KGlubGEuc21hcmdpbmFsKHJlcyRtYXJnaW5hbHMuaHlwZXJwYXJbWzFdXSksCiAgICAgeGxhYj0idGF1IiwgeWxhYj0iZGVuc2l0eSIsCiAgICAgbWFpbj0iUG9zdGVyaW9yIGZvciB0aGUgaHlwZXJwYXJhbWV0ZXIgdGF1IikKCnBsb3QoaW5sYS5zbWFyZ2luYWwoCiAgICAgICAgaW5sYS50bWFyZ2luYWwoZnVuY3Rpb24oeCkxL3NxcnQoeCksIAogICAgICAgICAgICByZXMkbWFyZ2luYWxzLmh5cGVycGFyW1sxXV0pKSwgCiAgICAgeGxhYj0ic2lnbWEiLCB5bGFiPSJkZW5zaXR5IiwKICAgICBtYWluPSJQb3N0ZXJpb3IgbWFyZ2luYWwgZm9yIHRyYW5zZm9ybWVkIGh5cGVycGFyYW1ldGVyIHNpZ21hIikKCiMgRkI6IFdoeSBpcyBtYXJnaW5hbHMucmFuZG9tIGVtcHR5Pz8gPSBiZXRhPz8KCmlubGEuem1hcmdpbmFsKGlubGEudG1hcmdpbmFsKGZ1bmN0aW9uKHgpMS9zcXJ0KHgpLHJlcyRtYXJnaW5hbHMuaHlwZXJwYXJbWzFdXSkpCmBgYAoKRkI6IFdoYXQgZG9lcyBhbGwgdGhpcyBtZWFuPy4uLi4uCgoKIyMgMy4yIEdMTU0gd2l0aCByYW5kb20gZWZmZWN0cwoKTGFzdCwgd2UgdXNlIElOTEEgdG8gYW5hbHlzZSB0aGUgIlNlZWRzIiBkYXRhIHNldC4KCmBgYHtyIEdMTU0xLCBlY2hvPUZBTFNFfQpsaWJyYXJ5KElOTEEpCiMgTG9hZCBkYXRhc2V0CmRhdGEoU2VlZHMpCgojIFByZXBhcmUgSU5MQSBjYWxsCmRhdGEgPSBTZWVkcwpmb3JtdWxhID0gciB+IHgxICsgeDIgKyBmKHBsYXRlLCBtb2RlbD0iaWlkIikKCiMgQ2FsbCBJTkxBCnJlcyA9IGlubGEoZm9ybXVsYT1mb3JtdWxhLCBkYXRhPWRhdGEsCiAgICAgICAgICAgZmFtaWx5PSJiaW5vbWlhbCIsIE50cmlhbHM9biwKICAgICAgICAgICBjb250cm9sLmZhbWlseSA9IGxpc3QobGluayA9ICJsb2dpdCIpLCAKICAgICAgICAgICBjb250cm9sLnByZWRpY3RvciA9IGxpc3QoY29tcHV0ZT1UUlVFKSkKCiMgUG9zdCBwcm9jZXNzaW5nCnN1bW1hcnkocmVzKQoKcGFyKG1mcm93PWMoMSwzKSkKcGxvdChpbmxhLnNtYXJnaW5hbChyZXMkbWFyZ2luYWxzLmZpeGVkW1sxXV0pLAogICAgIHhsYWI9IkludGVyY2VwdCIsIHlsYWI9ImRlbnNpdHkiLAogICAgIG1haW49IlBvc3RlcmlvciBtYXJnaW5hbCBmb3IgZml4ZWQgZWZmZWN0IikKCnBsb3QoaW5sYS5zbWFyZ2luYWwocmVzJG1hcmdpbmFscy5maXhlZFtbMl1dKSwKICAgICB4bGFiPSJhMSIsIHlsYWI9ImRlbnNpdHkiLAogICAgIG1haW49IlBvc3RlcmlvciBtYXJnaW5hbCBmb3IgZml4ZWQgZWZmZWN0IikKCnBsb3QoaW5sYS5zbWFyZ2luYWwocmVzJG1hcmdpbmFscy5maXhlZFtbM11dKSwKICAgICB4bGFiPSJhMiIsIHlsYWI9ImRlbnNpdHkiLAogICAgIG1haW49IlBvc3RlcmlvciBtYXJnaW5hbCBmb3IgZml4ZWQgZWZmZWN0IikKCgojIEZCOiBob3cgdG8gZ2V0IHBfaT8gT3Igd2hhdCBpcyBvZiBpbnRlcmVzdCBoZXJlPwpwYXIobWZyb3c9YygxLDEpKQpwbG90KHJlcyRzdW1tYXJ5LmZpdHRlZC52YWx1ZXMkbWVhbiwKICAgICB4bGFiPSJwbGF0ZSIsIHlsYWI9InAiLAogICAgIG1haW49IlBvc3RlcmlvciBtYXJnaW5hbCBtZWFuIGZvciBwIikKCmBgYA==